#include "array_and_file.c"
#include "swap.c"

/*PROTOTYPES*/
void heap_sort (int *heap_to_use, int heap_density, char *unsorted_input_file, char *sorted_output_file);
void heapify (int *array, int heap_size, char *file_name);
void percolate_down (int *array, int heap_size,  int element_index);
int get_least_child_index (int *array, int element_index);		//IMPORTANT: Make sure this function is NOT called on leaf nodes.
int delete_min (int *array, int *heap_size);
void insert_into_heap (int *array, int *heap_size, int number);		//IMPORTANT: Overflow and underflow are NOT taken care of.



/*FUNCTION DEFINITIONS*/


//STEP I: Call heapify().
//STEP II: Delete nodes one-by-one and place each deleted node's key in the output file.
void heap_sort (int *heap_to_use, int heap_density, char *unsorted_input_file, char *sorted_output_file)
{
	int i, j, heap_density_clone;
	FILE *ofp;

	heap_density_clone = heap_density;		//Since heap_density is passed later on by reference (and is modified), we create a clone.
	heapify (heap_to_use, heap_density, unsorted_input_file);
	ofp = fopen (sorted_output_file, "w");

	for (i = 0; i < heap_density; i++) {
		j = delete_min (heap_to_use, &heap_density_clone);
		fprintf (ofp, "%d\n", j);
	}

	fclose (ofp);
}



//Creates a min-heap out of numbers in 'unsorted_file'.
void heapify (int *heap, int heap_size, char *unsorted_file)		//heap_size expects appropriate file_size[] member.
{
	int element_to_adjust, last_element;

	last_element = heap_size - 1;		//Index of last element in the heap = heap_size - 1.
	read_file_into_array (heap, heap_size, unsorted_file);		//Creation of CBT in heap[].
	element_to_adjust = (last_element - 1) / 2;		//Index of element from which heap adjustment should begin.

	for (; element_to_adjust >= 0; element_to_adjust--)		//When element_to_adjust == 0, the root is being adjusted. We stop after that.
		percolate_down(heap, heap_size, element_to_adjust);
}



//Adjust 'element' until it is at the proper place in the CBT. Note that cbt[] will hold a min-heap after percolate_down is performed on all elements.
//This is done in heapify().
void percolate_down (int *cbt, int cbt_size, int index_of_element)
{
	int smallest_child, last_parent;

	last_parent = ((cbt_size - 1) - 1) / 2;		//Index of last internal node. cbt_size - 1 = last node. floor ((last_node - 1) / 2) = last internal node.

	while (index_of_element <= last_parent) {		//Making sure 'element' is not a leaf node. If 'element' is indeed a leaf node, it is now in place. Hence, we stop.
		smallest_child = get_least_child_index (cbt, index_of_element);		//Get index of the smallest child.

		if (cbt[index_of_element] > cbt[smallest_child]) {
			swap (&cbt[index_of_element], &cbt[smallest_child]);		//Call by ref.
			index_of_element = smallest_child;		//'element' now percolates down.
		}
		else break;		//Procedure completed if no further adjustments are required.
	}
}



//IMPORTANT: Make sure this function is NOT called on leaf nodes.
//Returns index of the smallest child.
int get_least_child_index (int *com_bin_tree, int element_index)
{
	int l_child, r_child;

	l_child = 2 * element_index + 1;
	r_child = 2 * element_index + 2;

	if (com_bin_tree[r_child] == 0)
		return l_child;		//All elements of the array are initialised to 0. If a child has value 0, it does not exist.
	else {
		if (com_bin_tree[l_child] < com_bin_tree[r_child])
			return l_child;
		else
			return r_child;
	}
}



int delete_min (int *heap, int *heap_size)	//Size of the heap is passed by reference since it needs to be altered after a deletion.
{
	int deleted_element, heap_size_dummy, last_parent, last_element, smallest_child_of_hole, hole = 0;	//Creation of 'hole' at the root.

	heap_size_dummy = *heap_size;
	deleted_element = heap[hole];		//Delete root.
	last_element = (heap_size_dummy) - 1;
	last_parent = (last_element - 1) / 2;

	while (1) {

		if (hole > last_parent) {		//If 'hole' is a leaf node, fill it with the last node.

			heap[hole] = heap[last_element];
			(*heap_size)--;
			break;
		}

		else {	//If 'hole' is internal,

			smallest_child_of_hole = get_least_child_index (heap, hole);

			if (heap[last_element] <= heap[smallest_child_of_hole]) {		// <= is important.
				heap[hole] = heap[last_element];		//'hole' is filled with the last element.
				(*heap_size)--;
				break;
			}

			else {
				heap[hole] = heap[smallest_child_of_hole];		//Percolate the 'hole' down. Note that percolate_down is not called.
				hole = smallest_child_of_hole;		//percolate_down adjusts an element based on its key value. We're not concerned with the hole's value here (it doesn't have one).
			}
		}
	}

	return deleted_element;
}



//IMPORTANT: Overflow and underflow are NOT taken care of.
void insert_into_heap (int *heap, int *heap_size, int item)
{
	int index_of_new_item, new_size;

	index_of_new_item = *heap_size;		//We'll not play around with pointers.
	new_size = *heap_size + 1;		//In the percolate_down below, we use this variable to avoid passing size by reference.

	heap[index_of_new_item] = item;
	percolate_down (heap, new_size, index_of_new_item);

	(*heap_size)++;
}
